#-*- coding: utf-8 -*-
# n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击
# 给定一个整数 n，返回 n 皇后不同的解决方案的数量

# 示例:
# 输入: 4
# 输出: 2
# 解释: 4 皇后问题存在如下两个不同的解法
# [
#  [".Q..",  // 解法 1
#   "...Q",
#   "Q...",
#   "..Q."],

#  ["..Q.",  // 解法 2
#   "Q...",
#   "...Q",
#   ".Q.."]
# ]

# 写给以后的自己，学习并记录一下python中作用域的问题
# 如一下的rtn变量
# 当rtn是int，并且不加global时，在backtrack中只能进行打印是没问题的，但是运行rtn += 1就无法找到变量
# 当rtn是list，并且不加global时，在backtrack中即可打印，又可运行rtn.append()
# 
# 当加上global后，即便rtn是int，在backtrack中，既能打印也能运行rtn += 1
# 为什么要增加2个global才行
class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        def backtrack(index):
            global rtn;
            if index == n:
                rtn += 1;
                return;

            for i in range(index, n):
                is_available = True;

                for j in range(index):
                    if index - j == abs(p_cols[i] - p_cols[j]):
                        is_available = False;
                        break;

                if not is_available:
                    continue;

                p_cols[index], p_cols[i] = p_cols[i], p_cols[index];
                backtrack(index + 1);
                p_cols[index], p_cols[i] = p_cols[i], p_cols[index];

        global rtn;
        rtn = 0;
        p_cols =[ i for i in range(n) ];
        backtrack(0);

        return rtn;


t = Solution();
print t.totalNQueens(5);